﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
#include<stdbool.h>
#include<stddef.h>//NULL
//int main()
//{
//	int a, b, c;
//	char d[20001];
//	scanf("%s", d);
//	a = strlen(d);
//	int e[26] = { 0 };
//	int g[26] = { 0 };
//	for (b = 0; b < a / 2; b++)
//	{
//		char f = d[b];
//		e[f - 'a']++;
//	}
//	for (b = a / 2; b < a; b++)
//	{
//		char f = d[b];
//		e[f - 'a']++;
//	}
//	for (b = 0; b < 25; b++)
//	{
//		for (c = 0; c < 25 - b; c++)
//		{
//			if (e[c] < e[c + 1])
//			{
//				int r = e[c];
//				e[c] = e[c + 1];
//				e[c + 1] = r;
//			}
//		}
//	}
//	for (b = 0; b < 25; b++)
//	{
//		for (c = 0; c < 25 - b; c++)
//		{
//			if (g[c] < g[c + 1])
//			{
//				int r = g[c];
//				g[c] = g[c + 1];
//				g[c + 1] = r;
//			}
//		}
//	}
//	int result = 0;
//	for (b = 1; b < 25; b++)
//	{
//		result += e[b];
//		result += g[b];
//	}
//	printf("%d", result);
//	return 0;
//}
//int main()
//{
//	long int a, b, c;
//	char d[200001];
//	scanf("%s", d);
//	a = strlen(d);
//	int e[26] = { 0 };
//	int g[26] = { 0 };
//	for (b = 0; b < a / 2; b++)
//	{
//		char f = d[b];
//		e[f - 'a']++;
//	}
//	for (b = a / 2; b < a; b++)
//	{
//		char f = d[b];
//		g[f - 'a']++;
//	}
//	for (b = 0; b < 25; b++)
//	{
//		for (c = 0; c < 25 - b; c++)
//		{
//			if (e[c] < e[c + 1])
//			{
//				long int r = e[c];
//				e[c] = e[c + 1];
//				e[c + 1] = r;
//			}
//		}
//	}
//	for (b = 0; b < 25; b++)
//	{
//		for (c = 0; c < 25 - b; c++)
//		{
//			if (g[c] < g[c + 1])
//			{
//				long int r = g[c];
//				g[c] = g[c + 1];
//				g[c + 1] = r;
//			}
//		}
//	}
//	long int result = 0;
//	for (b = 1; b < 26; b++)
//	{
//		result += e[b];
//		result += g[b];
//	}
//	printf("%ld", result);
//	return 0;
//}
//int main()
//{
//	int x;
//	char y[18];
//	scanf("%d %s", &x, y);
//	int c = strlen(y);
//	if (x == 1)
//	{
//		printf("%d", 1);
//	}
//	else if (x == 2)
//	{
//		printf("100000000");
//	}
//	else
//	{
//		printf("100000000000000000");
//	}
//	int i;
//	printf("%s", y);
//	return 0;
//}
//int main()
//{
//	int x;
//	long double y;
//	scanf("%d %Lf", &x, &y);
//	if (x == 1)
//	{
//		y += 1;
//	}
//	else if (x == 2)
//	{
//		y += 1000000000;
//	}
//	else
//	{
//		y += 1000000000000000000;
//	}
//	printf("%Lf", y);
//	return 0;
//}
////一共2的n次方-2种方法
//long long ou(long b)
//{
//	long long c = 1;
//	long i;
//	for (i = 1; i <= b; i++)
//	{
//		c *= i;
//		c %= 1000000007;
//	}
//	c = (c * c) % 1000000007;
//	c *= 2;
//	c %= 1000000007;
//	return c;
//}
//long long ji(long b)
//{
//	long long c = 1;
//	long i;
//	for (i = 1; i <= b; i++)
//	{
//		c *= i;
//		c %= 1000000007;
//	}
//	c = (c * (b + 1)) % 1000000007;
//	return c;
//}
//int main()
//{
//	long int a;
//	scanf("%ld", &a);
//	if (a % 2 == 0)
//	{
//		long b = a / 2;
//		long long c = ou(b);
//		printf("%lld", c);
//	}
//	else
//	{
//		long b = a / 2;
//		long long c = ji(b);
//		printf("%lld", c);
//	}
//	return 0;
//}
//bool jiushi(long long c)
//{
//	int a = 0;
//	while (c)
//	{
//		a += (c % 10);
//		c /= 10;
//	}
//	if (a % 3 == 0)
//	{
//		return true;
//	}
//	return false;
//}
//int main()
//{
//	long long i, c, j;
//	long long a[500000000];
//	long long b[500000000];
//	j = 0;
//	for (i = 1; i <= 4285714285; i++)
//	{
//		if(j<500000000)
//		{
//			if (i % 10 == 5)
//			{
//				a[j] = i;
//			}
//			else if (jiushi(i))
//			{
//				a[j] = i;
//			}
//			else
//			{
//				continue;
//			}
//		}
//		else
//		{
//			if (i % 10 == 5)
//			{
//				b[j] = i;
//			}
//			else if (jiushi(i))
//			{
//				b[j] = i;
//			}
//			else
//			{
//				continue;
//			}
//		}
//		j++;
//	}
//	scanf("%lld", &c);
//	while (c--)
//	{
//		long long e;
//		scanf("%lld", &e);
//		if(e<=500000000)
//		{
//			printf("%lld\n", a[e - 1]);
//		}
//		else
//		{
//			printf("%lld\n", b[e - 1]);
//		}
//	}
//	return 0;
//}
//bool jiushi(long long c)
//{
//	int a = 0;
//	while (c)
//	{
//		a += (c % 10);
//		c /= 10;
//	}
//	if (a % 3 == 0)
//	{
//		return true;
//	}
//	return false;
//}
//int main()
//{
//	long long i, c, j;
//	int x = 0;
//	long long a[500000000];
//	long long b[500000000];
//	j = 0;
//	for (i = 3; i <= 4285714285; i += 2)
//	{
//		if (j < 500000000 && x == 0)
//		{
//			if (i % 10 == 5)
//			{
//				a[j] = i;
//				j++;
//			}
//			else if (jiushi(i))
//			{
//				a[j] = i;
//				j++;
//			}
//			else
//			{
//				continue;
//			}
//		}
//		else
//		{
//			x = 1;
//			if (i % 10 == 5)
//			{
//				b[j - 500000000] = i;
//				j++;
//			}
//			else if (jiushi(i))
//			{
//				b[j - 500000000] = i;
//				j++;
//			}
//			else
//			{
//				continue;
//			}
//		}
//	}
//	for (i = 0; i < 500; i++)
//	{
//		printf("%lld ", a[i]);
//	}
//	//scanf("%lld", &c);
//	//while (c--)
//	//{
//	//	long long e;
//	//	scanf("%lld", &e);
//	//	if (e <= 500000000)
//	//	{
//	//		printf("%lld\n", a[e - 1]);
//	//	}
//	//	else
//	//	{
//	//		printf("%lld\n", b[e - 1 - 500000000]);
//	//	}
//	//}
//	return 0;
//}
//我们需要存储多种数据，所以用这个typedef可以把数据类型随意转化,但是我们为了方便，之后的讲解用的是int类型的变量
//typedef int SLTDataType;
////定义链表
//typedef struct SList
//{
//	SLTDataType data;
//	struct SList* next;
//}SLTNode;
////把链表名字改为SLTNode方便表示
////这个函数是为插入的数据申请空间的函数
////传的参数这是表示申请空间所存储的数据
//SLTNode* SLTBuyNode(SLTDataType x)
//{
//	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
//	if (newnode == NULL)
//	{
//		//申请内存空间失败
//		perror("malloc fail!");
//		exit(1);
//	}
//	newnode->data = x;
//	newnode->next = NULL;
//	//当我们没有存储任何数据的时候不能随便放入SList里面的结构体指针为地址，这样会报错
//	return newnode;
//	//需要返回这个地址否则不知道新申请的空间是什么
//}
////void SLTPushBack(SLTNode* phead, SLTDataType x)
////{
////    SLTNode* newnode = SLTBuyNode(x);
////    if (phead == NULL)
//    {
//        //链表里面没有任何数据，直接把这个新申请的地址给变量
//        phead = newnode;
//    }
//    else
//    {
//        SLTNode* ptail = phead;
//        //我们需要寻找到最后一个结点的位置，但是我们不能改变phead的指向，否则无法知道链表的首地址在哪里，所以我们需要创建一个新的结构体指针变量
//        while (ptail->next != NULL)
//        {
//            //循环条件我们也可以写为ptail->next,这样遇到空指针也会结束循环
//            //其中我们可以看做最后一个结点的结构体指针为NULL，所以我们可以这样判断
//            ptail = ptail->next;
//        }
//        ptail->next = newnode;
//    }
//}
//尾插
//void SLTPushBack(SLTNode** pphead, SLTDataType x)
//{
//	SLTNode* newnode = SLTBuyNode(x);
//	if (*pphead == NULL)
//	{
//		//链表里面没有任何数据，直接把这个新申请的地址给变量
//		*pphead = newnode;
//	}
//	else
//	{
//		SLTNode* ptail = *pphead;
//		//我们需要寻找到最后一个结点的位置，但是我们不能改变phead的指向，否则无法知道链表的首地址在哪里，所以我们需要创建一个新的结构体指针变量
//		while (ptail->next != NULL)
//		{
//			//循环条件我们也可以写为ptail->next,这样遇到空指针也会结束循环
//			//其中我们可以看做最后一个结点的结构体指针为NULL，所以我们可以这样判断
//			ptail = ptail->next;
//		}
//		ptail->next = newnode;
//	}
//}
////头插
//void SLTPushFront(SLTNode** pphead, SLTDataType x)
//{
//	assert(pphead);
//	//如果pphead为空指针，我们无法从开始位置插入
//	SLTNode* newnode = SLTBuyNode(x);
//	newnode->next = *pphead;
//	*pphead = newnode;
//}
////打印链表元素
//void SLTPrint(SLTNode* phead)
//{
//	SLTNode* pcur = phead;
//	//我们不能改变phead的指向
//	while (pcur != NULL)
//	{
//		if (pcur->next != NULL)
//		{
//			printf("%d->", pcur->data);
//			pcur = pcur->next;
//		}
//		else
//		{
//			printf("NULL\n");
//			break;
//		}
//	}
//}
//在链表中查找数据，并返回找到数据的地址
//SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
//{
//	//我们不需要改变链表里面的数据，所以不用传址操作
//	assert(phead);
//	SLTNode* pcur = phead;
//	while (pcur)
//	{
//		if (pcur->data == x)
//		{
//			return pcur;
//		}
//	}
//	return NULL;
//}
////在指定位置之前插入数据
////void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
////{
////    assert(pphead);
////    assert(pos);
////    //pos不能为空指针
////    SLTNode* newnode = SLTBuyNode(x);
////    SLTNode* prev = *pphead;
////    while (prev->next != pos)
////    {
////        prev = prev->next;
////    }
////    newnode->next = pos;
////    prev->next = newnode;
////}
//void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
//{
//	if (*pphead == pos)
//	{
//		SLTPushFront(pphead, x);
//	}
//	else
//	{
//		assert(pphead);
//		assert(pos);
//		//pos不能为空指针
//		SLTNode* newnode = SLTBuyNode(x);
//		SLTNode* prev = *pphead;
//		while (prev->next != pos)
//		{
//			prev = prev->next;
//		}
//		newnode->next = pos;
//		prev->next = newnode;
//	}
//}
////在指定位置之后插入数据
//void SLTInsertAfter(SLTNode* pos, SLTDataType x)
//{
//	//由于链表可以自己往后查找，所以我们不需要传入plist
//	assert(pos);
//	SLTNode* newnode = SLTBuyNode(x);
//	newnode->next = pos->next;
//	pos->next = newnode;
//	//即使我们是在最后一个结点插入数据，相当于pos->node=NULL
//	//而插入之后我们的newnode=NULL了，故不需要分情况讨论
//}
////尾删函数
//void SLTPopBack(SLTNode** pphead)
//{
//	assert(*pphead);
//	//如果是空链表，则不能删除数据
//	assert(pphead);
//	//不能传递空指针
//	SLTNode* ptail = *pphead;
//	SLTNode* prev = NULL;
//	while (ptail->next)
//	{
//		prev = ptail;
//		//假设下一个结点就是尾结点，这个循环结束了，就找不到尾结点之前的结点了，所以要先把这个地址存起来
//		ptail = ptail->next;
//		//顺序不能调换
//	}
//	prev->next = NULL;
//	free(ptail);
//	ptail = NULL;
//}
////头删
//void SLTPopFront(SLTNode** pphead)
//{
//	assert(pphead && *pphead);
//	SLTNode* prev = *pphead;
//	*pphead = (*pphead)->next;
//	//一定要加括号，->的优先级高于*
//	free(prev);
//	prev = NULL;
//}
//////指定位置删除pos结点
////void SLTErase(SLTNode** pphead, SLTNode* pos)
////{
////    assert(pphead && pos);
////    SLTNode* prev = *pphead;
////    while (prev->next)
////    {
////        prev = prev->next;
////    }
////    prev->next = pos->next;
////    free(pos);
////    pos = NULL;
////}
////指定位置删除pos结点
//void SLTErase(SLTNode** pphead, SLTNode* pos)
//{
//	assert(pphead && pos);
//	if (pos == *pphead)
//	{
//		SLTPopFront(pphead);
//	}
//	else
//	{
//		SLTNode* prev = *pphead;
//		while (prev->next)
//		{
//			prev = prev->next;
//		}
//		prev->next = pos->next;
//		free(pos);
//		pos = NULL;
//	}
//}
////删除pos结点之后的那个结点
//void SLTEraseAfter(SLTNode* pos)
//{
//	assert(pos);
//	assert(pos->next);
//	SLTNode* del = pos->next;
//	pos->next = del->next;
//	//这前面两行代码比较难看懂，这个时候可以画图上去
//	free(del);
//	del = NULL;
//}
////销毁链表
//void SListDestroy1(SLTNode** pphead)
//{
//	SLTNode* pcur = NULL;
//	while (*pphead)
//	{
//		pcur = *pphead;
//		*pphead = (*pphead)->next;
//		free(pcur);
//	}
//}
////销毁链表的另外一种写法
//void SListDestroy2(SLTNode** pphead)
//{
//	SLTNode* pcur = *pphead;
//	while (pcur)
//	{
//		pcur = *pphead;
//		*pphead = (*pphead)->next;
//		free(pcur);
//	}
//}
////销毁链表的第三种方法，这个方法不需要*pphead直接参与，但是空间复杂度较大，需要创建好几次临时变量
//void SListDestroy3(SLTNode** pphead)
//{
//	SLTNode* pcur = *pphead;
//	while (pcur)
//	{
//		SLTNode* next = pcur->next;
//		free(pcur);
//		pcur = NULL;
//	}
//	*pphead = NULL;
//	//这个时候*pphead指向的地址已经不存在了，需要置为空指针
//}
//int main()
//{
//	SLTNode* plist = NULL;
//	//测试申请内存的函数
//	plist = SLTBuyNode(1);
//	//测试尾插函数
//	SLTPushBack(&plist, 1);
//	//测试头插函数
//	SLTPushFront(&plist, 2);
//	//测试查找函数
//	SLTNode* find = SLTFind(plist, 2);
//	//测试插入函数1
//	//SLTInsert(&plist, find, 3);
//	//SLTInsert(&plist, find, 5);
//	//测试插入函数2
//	SLTInsertAfter(find, 4);
//	//测试尾删函数
//	//SLTPopBack(&plist);
//	//测试头删函数
//	SLTPopFront(&plist);
//	//测试指定位置删除的函数
//	find = SLTFind(plist, 4);
//	SLTErase(&plist, find);
//	SLTPushFront(&plist, 3);
//	SLTPushBack(&plist, 2);
//	find = SLTFind(plist, 3);
//	//测试指定位置之后的结点删除的函数
//	SLTEraseAfter(find);
//	SLTPrint(plist);
//	return 0;
//}
typedef long long int SLTDataType;
//定义链表
typedef struct SList
{
	SLTDataType data;
	struct SList* next;
}SLTNode;
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* ptail = *pphead;
		while (ptail->next != NULL)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}
bool jiushi(long long c)
{
	int a = 0;
	while (c)
	{
		a += (c % 10);
		c /= 10;
	}
	if (a % 3 == 0)
	{
		return true;
	}
	return false;
}
int main()
{
	SLTNode* plist = NULL;
	long long i, c, j;
	int x = 0;
	j = 0;
	for (i = 3; i <= 4285714285; i += 2)
	{
		if (i % 10 == 5)
		{
			SLTPushBack(&plist, i);
		}
		else if (jiushi(i))
		{
			SLTPushBack(&plist, i);
		}
		else
		{
			continue;
		}
		j++;
		if (j == 1000000000)
		{
			break;
		}
	}
	scanf("%lld", &c);
	while (c--)
	{
		long long e;
		scanf("%lld", &e);
		if (e % 2 == 0)
		{
			e--;
			SLTNode* op = plist;
			while (e--)
			{
				op = op->next;
			}
			printf("%lld", op->data);
		}
		else
		{
			e--;
			SLTNode* op = plist;
			while (e -= 2)
			{
				op = op->next->next;
			}
			printf("%lld", op->data);
		}
	}
	return 0;
}